<?php
// This file is part of Moodle - http://moodle.org/
//
// Moodle is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <http://www.gnu.org/licenses/>.
/**
 * Build binary tree for Calculate Expressions
 * 
 * @package    questions
 * @category   Calculate Expression
 * @copyright  2014 Quoc Dai
 * @author	   Quoc Dai, Volgograd State Technical University
 * @license    http://www.gnu.org/copyleft/gpl.html GNU Public License
 */

require_once($CFG->dirroot.'/question/type/cppexpression/qtype_cppexpression_binary_tree.php');
require_once($CFG->dirroot.'/blocks/formal_langs/language_cpp_parseable_language.php');

/**
* 
*/
class qtype_cppexpression_create_tree
{
	private $expression;

	function __construct($string)
	{
		$this->expression = $string;
	}

	public function get_binary_tree(){
		$parserTree = self::make_from_string($this->expression);
		$parserTree[0] = self::delete_brackets($parserTree[0]);
		$tree = self::create_tree($parserTree[0]);

		return $tree;
	}

	/**
	 * create a node of binary tree from string
	 * @param string $expression
	 * @param int $current_pos
	 * @return node|qtype_cppexpression_binary_tree
	 */
	static function create_node($expression, $current_pos)
	{
		switch ($expression) {
			case '+':
			 	$node = new qtype_cppexpression_node_plus();
				$node->pos = $current_pos;
				 	
			 	break;

			case '-':
				$node = new qtype_cppexpression_node_sub();
				$node->pos = $current_pos;

				break;

			case '*':
				$node = new qtype_cppexpression_node_mul();
				$node->pos = $current_pos;

				break;

			case '/':
				$node = new qtype_cppexpression_node_div();
				$node->pos = $current_pos;

				break;

			case '%':
				$node = new qtype_cppexpression_node_percent();
				$node->pos = $current_pos;

				break;

			case '>':
				$node = new qtype_cppexpression_node_greater();
				$node->pos = $current_pos;

				break;

			case '<':
				$node = new qtype_cppexpression_node_less();
				$node->pos = $current_pos;

				break;

			case '>=':
				$node = new qtype_cppexpression_node_greater_or_equal();
				$node->pos = $current_pos;

				break;

			case '<=':
				$node = new qtype_cppexpression_node_less_or_equal();
				$node->pos = $current_pos;

				break;

			case '==':
				$node = new qtype_cppexpression_node_equal();
				$node->pos = $current_pos;

				break;

			case '!=':
				$node = new qtype_cppexpression_node_different();
				$node->pos = $current_pos;

				break;

			case '&&':
				$node = new qtype_cppexpression_node_and();
				$node->pos = $current_pos;

				break;

			case '||':
				$node = new qtype_cppexpression_node_or();
				$node->pos = $current_pos;

				break;

			case '!':
				$node = new qtype_cppexpression_node_not();
				$node->pos = $current_pos;

				break;

			case '|':
				$node = new qtype_cppexpression_node_or_bit();
				$node->pos = $current_pos;

				break;

			case '&':
				$node = new qtype_cppexpression_node_and_bit();
				$node->pos = $current_pos;

				break;

			case '^':
				$node = new qtype_cppexpression_node_xor_bit();
				$node->pos = $current_pos;

				break;

			case '~':
				$node = new qtype_cppexpression_node_not_bit();
				$node->pos = $current_pos;

				break;

			case '<<':
				$node = new qtype_cppexpression_node_left_shift();
				$node->pos = $current_pos;

				break;

			case '>>':
				$node = new qtype_cppexpression_node_right_shift();
				$node->pos = $current_pos;

				break;

			default:
				$node = new qtype_cppexpression_node_parameter($expression);
				$node->pos = $current_pos;
				$node->data = floatval($expression);
		}

		return $node;
	}

	/**
     * Optimizes tree replacing nodes with one child with their child
     * @param array|block_formal_langs_processed_string $nodes nodes
     * @return array optimized array of trees
     */
	static function optimize_tree($nodes) {
    
	    if (is_a($nodes, 'block_formal_langs_processed_string')) {
	        $nodes->set_syntax_tree(self::optimize_tree($nodes->syntaxtree));
	    }
	    if (is_array($nodes)) {
	        $nodes = array_values($nodes);
	        $changed = true;
	        while($changed) {
	            $changed = false;
	            if (count($nodes)) {
	                /** @var block_formal_langs_ast_node_base $node */
	                foreach($nodes as $key => $node) {
	                    if (count($node->childs()) == 1) {
	                        $children = $node->childs();
	                        /** @var block_formal_langs_ast_node_base $child */
	                        $child = $children[0];
	                        $nodes[$key] = $child;
	                        $changed = true;
	                    }
	                }
	            }
	        }
	        if (count($nodes)) {
	            foreach($nodes as $node) {
	                $node->set_childs(self::optimize_tree($node->childs()));
	            }
	        }
	    }
	    return $nodes;
	}


	/**
	 * Makes a tree from string
	 * @param string $string
	 * @return array
	 */
	public function make_from_string($string) {
	    $lang = new block_formal_langs_language_cpp_parseable_language();
	    $processedstring = $lang->create_from_string($string);
	    self::optimize_tree($processedstring);
	    return $processedstring->syntaxtree;
	}


	/**   
	 * delete all bracket in expression
	 * @param string $string
	 * @return array
	 */
	public function delete_brackets($string)
	{
		if ( $string == NULL || $string->childs() ==  NULL) {
			return $string;
		}
		
		if ($string->type() == 'expr_atom') {
			$string = $string->childs[1];
		}

		for ($i=0; $i < count($string->childs); $i++) { 
			$string->childs[$i] = self::delete_brackets($string->childs[$i]);
		}

		return $string;
	}


	/**
	 * Makes a binary tree from array nodes
	 * @param array $parserTree - array node extends from class 
	 * @param node|qtype_cppexpression_binary_tree $tree - current node
	 * @param node|qtype_cppexpression_binary_tree $parent_tree - parent of current node
	 * @return node|qtype_cppexpression_binary_tree - result tree
	 */
	public function create_tree($parserTree){

		if ($parserTree == NULL ) {
			return NULL;
		}

		if ( $parserTree->childs() == NULL) {
			$tree = self::create_node($parserTree->value()->string(), $parserTree->token_index());
			
			return $tree;
		}

		if (count($parserTree->childs()) == 3) {
			$tree = self::create_node($parserTree->childs[1]->value()->string(), $parserTree->childs[1]->token_index());
						
			$tree->childLeft = self::create_tree($parserTree->childs[0]);
			
			if ($tree->childLeft) {
				$tree->childLeft->set_parent($tree);
			}

			$tree->childRight = self::create_tree($parserTree->childs[2]);
			
			if ($tree->childRight) {
				$tree->childRight->set_parent($tree);
			}
		}

		if (count($parserTree->childs()) == 2) {
			$tree = self::create_node($parserTree->childs[0]->value()->string(), $parserTree->childs[0]->token_index());
			
			$tree->childLeft = self::create_tree($parserTree->childs[1]);
			
			if ($tree->childLeft) {
				$tree->childLeft->set_parent($tree);
			}
		}

		return $tree;
	}
}

?>